package trieSimple;
/**
* email: hanzack@163.com
* author: zack
**/

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.concurrent.CopyOnWriteArrayList;




public class TrieSimple implements Serializable{

    /**
     * 
     */
    private static final long serialVersionUID = -2933923081228664509L;
    /**
     * 
     */
    // 创建root
    public TrieNode rootNode;
    
    public int nodeNum = 0;
    
    //构建trie 这个数据结构
    public TrieSimple(){
        rootNode=new TrieNode('#');
    }
    
     /**
      * 添加一个词进入字典。 
     * @param word
     */
//  public void insert(String word){  
//          if(search(word) == true)
//              return;  
//          Trie_Nodes current = rootNodes;  
//          for(int i = 0; i < word.length(); i++){
//              Trie_Nodes child = current.subNodes(word.charAt(i));
//              if(child != null){   //如果存在这个子节点， 就去看子节点的子节点
//                  current = child;  
//              } else { 
//                  current.childNodes.add(new Trie_Nodes(word.charAt(i)));
//                  current=current.subNodes(word.charAt(i));
//              }  
//              current.preFixFreq++;  
//          }   
//          current.isEnd = true;  
//      }  
//  
    
    
    
    
    
     /**
      * 添加一个词进入字典。 
     * @param word
     */
    public void insert(String word){  
            if(search(word) == true)
                return;  
            TrieNode current = rootNode;   //获取跟节点
            for(int i = 0; i < word.length(); i++){
                TrieNode child = current.subNodes(word.charAt(i));  //获取当前节点的子节点。  
                if(child != null){   //如果存在这个子节点， 就去看子节点的子节点
                    current = child;  
                } else {  //如果不存在这个子节点 ， 就新建这个子节点， 并转移指针到子节点。 
                    current.childNodes.add(new TrieNode(word.charAt(i)));
                    current=current.subNodes(word.charAt(i));
                }  
                current.preFixFreq++;  
            }   
            // 设置这个词的最后一个字符的节点的isEnd为true。 
            current.isEnd = true;  
        }  
    
     
     
     
     /**
      * 
     * 传入一个字符串判断这个树中是否包含这个词。
     * @param word
     * @return
     */
    public boolean search(String word){
         TrieNode currNodes=rootNode;

         for (int i = 0; i < word.length(); i++) {
             TrieNode tempNodes=currNodes.subNodes(word.charAt(i));  //判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
             if (tempNodes != null) {//判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
                currNodes=tempNodes;
            }else{
                return false;
            }
        }
         if (currNodes.isEnd) {
            return true;
        }
         return false;
     }
     
    
     /**
     * 
     * 传入一个字符串判断这个树中是否包含这个词,如果包含这个词，就返回这个词最后一个字母所在的节点。 
     * @param word
     * @return
     */
    public TrieNode searchWordRtNode(String word){
         TrieNode currNodes=rootNode;
         for (int i = 0; i < word.length(); i++) {
             TrieNode tempNodes=currNodes.subNodes(word.charAt(i));  //判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
             if (tempNodes != null) {//判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
                currNodes=tempNodes;
            }else{
                return null;
            }
        }
         if (currNodes.isEnd) {
            return currNodes;
        }
         return null;
     }
    
    
    
    
    
    

     /**
     * 判断是否包含某一前缀（可以是前缀，也可以是词）。 例如，appl   可以得到这个字符串最后一个字母的节点。l的isEnd不需要为true
     * 传入一个字符串判断这个树中是否包含这个字符串，,如果包含这个词，就返回这个词最后一个字母所在的节点。 
     * @param word
     * @return
     */
    public TrieNode searchPrefixRtNode(String word){
         TrieNode currNodes=rootNode;
         for (int i = 0; i < word.length(); i++) {
             TrieNode tempNodes=currNodes.subNodes(word.charAt(i));  //判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
             if (tempNodes != null) {//判断当前节点的子节点里有没有一个  字符是   word.charAt(i)
                currNodes=tempNodes;
            }else{
                return null;
            }
        }
         return currNodes;
     }
    
    
    
    
    
    
    
    
    
    
    
    /**
     * 从Trie词典中删除某个词。 
     * 原理：  例如要删除     number ,   我们要先删除r，再删除e， 删除r是指，如果到r，它仍然有子节点， 那么说明有词语的前缀是number，
     * 因此不能删掉r， 只需要修改r这个节点的frequency， isEnd 从true 改为false。  也就是说原来 number是个词（同时是个前缀），现在number不是词了，只是前缀。
     * 对于e，我们也要像上面那样处理，唯一区别是 ，不用考虑numbe 是否是一个词。 
     * 。
     * 下面的实现方法采用的是： 递归方式。
     * 要处理n，必须先处理u，，，，如果处理到最后一个字母的时候，处理完返回。
     * 每次递归的参数：  List<Trie_Nodes> pareList,      Trie_Nodes tNode,            int countDelete,               String originWord
     * paraList  是指包含当前节点的数组。 这个数组需要从当前节点的父节点.childNodes来获得。     tNode: 当前节点。  countDelete: 指删除到第几个了。     originWord: 就是需要添加的这个单词。 
     * 
     * 这个删除方式可以避免内存溢出
     * @param word
     */
    public void deleteWordVersion2(String word){ 
        //首先判断这个词是否存在
        if(search(word) == false) 
            return;  
        TrieNode firstNode=rootNode.subNodes(word.charAt(0));
        deleteWordRecursive(rootNode.childNodes,firstNode,0,word);
       
    }  
    
    
    
    
    public void deleteWordRecursive(List<TrieNode> pareList,TrieNode tNode, int countDelete,String originWord){
        //一共需要删除 word.length词。 判断当前删除到第几个。 如果是删除了最后一个了则返回。
        if (countDelete == originWord.length()-1) {//如果删除到最后一个了。 
            if (null != tNode.childNodes && tNode.childNodes.size()>0) {//如果最后一个要删除的节点  有子节点的话， 就不删除它，而是修改它的frequency-1
                if (tNode.preFixFreq>0) {
                    tNode.preFixFreq=tNode.preFixFreq-1;    
                    tNode.isEnd=false;
                }
            }else{//如果最后一个要删除的节点没有子节点，则
                pareList.remove(tNode);
            }
        }
        //删除当前字符串的子字符串delete()，,判断当前节点的子节点的个数， 当前节点的freq-1   
        else {
            List<TrieNode> tempParaList=pareList;
            TrieNode tempTNode = tNode;
            int tempNodeSubSize=0;
            if (null != tempTNode.childNodes) {//
                 tempNodeSubSize=tempTNode.childNodes.size();
            }
            
            pareList = tNode.childNodes;
            tNode=tNode.subNodes(originWord.charAt(countDelete));
            deleteWordRecursive(pareList, tNode,  countDelete+1, originWord);
            
            //处理递归之前的内容
            if (tempNodeSubSize>1) {//如果这个节点子节点的个数大于1， 我们就不能删除它,只能修改它的frequency
                tempTNode.preFixFreq=tempTNode.preFixFreq-1;
            }else{
                tempParaList.remove(tempTNode);//直接删除
            }
        }
        
    }
    
    
    
    
    /**
     * 从Trie 树中删除节点。 这种删除方式会造成内存溢出，并不科学。 
     * @param word
     */
    public void deleteWord(String word){  
        if(search(word) == false) return;  
      
        TrieNode current = rootNode;  
        for(char c : word.toCharArray()) {   
            TrieNode child = current.subNodes(c);  
            if(child.preFixFreq == 1) {  
                current.childNodes.remove(child);  
                return;  
            } else {  
                child.preFixFreq--;  
                current = child;  
            }  
        }  
        current.isEnd = false;  
    }
    
    
    
     /**
      * 传入一个字符串判断这个树中是否包含这个词。 
     * @param word
     * @return
     */
    public boolean search普通版本(String word){
         TrieNode curr=rootNode;
         int k=0;
        while(curr.childNodes!=null){
            if (k>=word.length()) {
                if (curr.isEnd) { //需要判断， 虽然有了这个词语但是还要看这个词语仅仅是前缀还是，也是一个词语？因此要判断  isEnd这个属性。 
                    return true;
                }else{
                    return false;
                }
            }
            for (TrieNode tNode:curr.childNodes) {
                if ((tNode.nodeChar+"").equals(word.substring(k,k+1))) {//搜节点的第x层的是否有个字符和word 的第x个字符相等。 是就继续， 否返回false;
                    curr=tNode;
                }else {
                    return false;
                }
            }
            k++;
        }
         return false;
     }
     
    
    
    
    /* 打印当前树种的所有单词组合。 
     * (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString(){
        String allWordsString="";
        getAllWordFromTrie();
        List<List<TrieNode>> printNodeList =getAllWordFromTrie();
        for (List<TrieNode> nodeList:printNodeList) {
            for (TrieNode node:nodeList) {
                allWordsString=allWordsString+node.nodeChar;
            }
            allWordsString=allWordsString+"\r\n";
        }
        
        return allWordsString;
        
    }
    
    
    
    /* 重写toString方法
     * @see java.lang.Object#toString()
     */
    public List<List<TrieNode>> getAllWordFromTrie(){
        LinkedList<TrieNode> printNodeList=new LinkedList<>();
        printNodeList.add(rootNode);
        //循环
        List<List<TrieNode>> wordsList = new LinkedList<>();
        dfs_Trie(printNodeList,rootNode,1,wordsList);
        return wordsList;
    }
    
    
    /**
     * 利用深度优先获取Trie树的每一个路径。
     * 先设置输出和终止条件。 
     * 然后for循环每一个节点的所有子节点， 找到一个子节点就进入下一层循环,等返回之后再进行本次的其他循环。 
     * wordcount 表示第几层。 
     */
    public void dfs_Trie(LinkedList<TrieNode>  printNodeList,TrieNode currNode,int wordCount, List<List<TrieNode>> wordsList){
    
        if (currNode.isEnd) {
//          printWordFromList(printNodeList);
            List<TrieNode> tempList=new LinkedList<>();
            for (TrieNode tN:printNodeList) {
                tempList.add(tN);
            }
            wordsList.add(tempList);
        }
        //如果到了叶子节点。 // 注意这里必须要设置一个 currNode.childNodes.size()==0   因为叶子节点也有一个不为null的childNodes
        if(null == currNode.childNodes || currNode.childNodes.size()==0){  
            return;
        }
        
        for (int k=0; k<currNode.childNodes.size();k++) {
            TrieNode tempCurrNode=currNode.childNodes.get(k);
            //把这个node加入到list里面去，这个list里面存放的是单词
            printNodeList.add(tempCurrNode);
            dfs_Trie(printNodeList,tempCurrNode,wordCount+1,wordsList);
            printNodeList.remove(tempCurrNode);
//          dfs_Trie(printNodeList,tempCurrNode,wordCount);
        }
    }
    
    
    /**
     * 打印节点链表单词
     */
    public static String printWordFromList(LinkedList<TrieNode> nodes){
        String wordsString="";
        for (TrieNode tnode:nodes) {
            wordsString=wordsString+tnode.nodeChar;
            System.out.print(tnode.nodeChar);
        }   
        return wordsString;
    }
    

    /**
     * 传入一个对象，一个文件名， 把对象序列化到文件名里面去。 
     * @param filePath
     * @param trieObj
     */
    public static void getSerialize(String filePath, TrieSimple trieObj) {
        if (null==filePath || filePath.equals("") || filePath.equals(" ")) {
            filePath="doc/abc.txt";
        }
        try {
            //首先是创建一个file，然后封装到outputStream里面，然后封装如objectOutputStream
            File file=new File(filePath);
            ObjectOutputStream objStream=new ObjectOutputStream(new FileOutputStream(file));
            //建立一个对象，准备把它序列化
            
            objStream.writeObject(trieObj);
            objStream.flush();
            objStream.close();
             
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } 
        System.out.println("Finish Serializable ！");
    }
    
     /**
     * @return
     * 第一种压缩方式： 
     * 压缩Trie树， 把连续的节点压缩成一个（当连续的节点都没有其他节点相连的时候，也就是说可以被压缩的节点必须满足， freq=1）
     * 例如   abcde， 与  abckx 如果trie只有这两个词， 那么  d与e可以被压缩到一个节点里面，  k，x 可以被压缩到一个节点里，
     * 而a与b与c则不能做这个压缩， 因为，他们的出现频率都不是1
     * 
     * 第二种压缩方式：
     * 只要这个节点的子节点个数为1， 把这样连续的子节点进行压缩，直到压缩到最后一个 子节点个数为1的节点的子节点。 
     * 例如A的子节点个数为1也就是B， 那么无论B有几个子节点，都可以把A和B压缩到一个节点里面去。 
     * 
     * 注意有些节点如果是结束节点则不应该进行压缩。
     * 一旦压缩好的Trie树，是不允许动态添加节点和删除节点的。 
     */
    public static TrieSimple compactTrie(TrieSimple aTrie){
//        logger.info("Before compressing: "+aTrie.nodeNum+"\nCompressing the Trie...");
        long a = System.currentTimeMillis();
        PriorityQueue<TrieNode> nodesQueue = new PriorityQueue<>(new Comparator<TrieNode>() {
            @Override
            public int compare(TrieNode o1, TrieNode o2) {
                return 0;
            }
        });
        if (null == aTrie.rootNode || aTrie.rootNode.getChildNodes().size() < 1) {
            return aTrie;
        }
        nodesQueue.addAll(aTrie.rootNode.getChildNodes());
        
        StringBuilder compactStr = new StringBuilder();
        while (nodesQueue.size() > 0) {
            TrieNode currentNode = nodesQueue.poll();
            TrieNode fatherNode = currentNode.fatherNode;
            TrieNode tempCurrentNode = currentNode;
            TrieNode newNode = new TrieNode('\0');
            compactStr.setLength(0);
            int cntNum = 0;
            compactStr.setLength(0);
            while(currentNode.childNodes.size() == 1 && !currentNode.isEnd){
                cntNum++;
                compactStr.append(currentNode.nodeChar);
                
                //记录当前节点，把所有连续的这种节点组合成一个节点。 
                currentNode = currentNode.childNodes.get(0);
            }
            if (cntNum >= 1) {
                aTrie.nodeNum = aTrie.nodeNum-cntNum;
               // 1. 把currentNode的信息赋值给newNode里面
                compactStr.append(currentNode.nodeChar);
                newNode.isEnd = currentNode.isEnd;
                newNode.fatherNode = fatherNode;
                
                newNode.setCompactStr(compactStr.toString());
                newNode.preFixFreq=currentNode.preFixFreq;
//                newNode.setCuiList(currentNode.cuiList);
                newNode.setWholeWord(currentNode.wholeWord);
               // 2. 从father的子节点里把tempCurrentNode删除，  然后添加引用指向newNode
                CopyOnWriteArrayList<TrieNode> cowList = new CopyOnWriteArrayList<>(fatherNode.childNodes);
                for(TrieNode trieNode : cowList){
                    if (trieNode == tempCurrentNode) {
                        cowList.remove(trieNode);
                    }
                }
                cowList.add(newNode);
                LinkedList<TrieNode> childNodes = new LinkedList<>(cowList);
                fatherNode.setChildNodes(childNodes);
                
               // 3. 把current子节点赋值给newNode 
                newNode.setChildNodes(currentNode.childNodes);
                //4. 还要把所有子节点的父节点全部改成newNode
                for(TrieNode trieNode : newNode.childNodes){
                    trieNode.setFatherNode(newNode);
                }
            }else{
                //清理掉内存
                newNode = null;
            }
            //这里再把子节点给添加进入queue里面， 也可以写成newNode,而不应该用currentNode，前提是null!=newNode
            if (null != newNode && null!=newNode.childNodes && newNode.childNodes.size() >=0) {
                nodesQueue.addAll(newNode.childNodes);
            } else if (null != currentNode && null!=currentNode.childNodes && currentNode.childNodes.size() >=0) {
                nodesQueue.addAll(currentNode.childNodes);
            }
        }
        long b = System.currentTimeMillis();
//        logger.info("Finishing compressing......"+aTrie.nodeNum+"     -----------Compressing Time Cost: "+(b-a)+" ms.");
        return aTrie;
    }
    
    
    
    /**
     * @param serializeFile
     * @return
     */
    public static TrieSimple fanxuliehua(String serializeFile){
        if (null == serializeFile || serializeFile.equals("") || serializeFile.equals(" ")) {
            System.err.println("Your file is not a serialized File.");
        }
        ObjectInputStream oin=null;
        try {
            oin=new ObjectInputStream(new FileInputStream(serializeFile));
            TrieSimple trieObj=(TrieSimple) oin.readObject();
            oin.close();
            return trieObj;
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } 
        return null;
    }
    
    
}

